'''
参考： https://blog.csdn.net/weixin_45758642/article/details/122945316
'''

from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x  # 值
        self.left = None  # 左节点
        self.right = None  # 右节点


def level_order_tree(root:TreeNode) :
    '''
    输出结果 从上到下，从左到右
    '''
    if not root:  # 为 None 就返回[]
        return []
    queue = []
    result = []
    queue.append(root)  # 将根节点入队
    while len(queue) > 0:
        node = queue.pop(0)  # 取队列队首
        result.append(node.val)
        # 判断左右子树
        if node.left:  # 添加左子树的孩子到队列
            queue.append(node.left)
        if node.right:  # 添加右子树的孩子到队列
            queue.append(node.right)
    return result  #List


if __name__ == "__main__":
    tree = TreeNode(4)
    tree.left = TreeNode(9)
    tree.right = TreeNode(0)
    tree.left.left = TreeNode(5)
    tree.left.right = TreeNode(1)
    tree.right.left = TreeNode(3)
    tree.right.right = TreeNode(2)
    tree.left.left.left = TreeNode(10)
    tree.right.left.right = TreeNode(7)

    print(level_order_tree(tree))
    # [4, 9, 0, 5, 1, 3, 2, 10, 7]


